#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
use std::mem;
use crate::alloc_testing::*;
extern "C" {
        }
pub type size_t = libc::c_ulong;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _RBTree {
    pub root_node: *mut RBTreeNode,
    pub compare_func: RBTreeCompareFunc,
    pub num_nodes: libc::c_int,
}
pub type RBTreeCompareFunc = Option::<
    unsafe extern "C" fn(RBTreeValue, RBTreeValue) -> libc::c_int,
>;
pub type RBTreeValue = *mut libc::c_void;
pub type RBTreeNode = _RBTreeNode;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _RBTreeNode {
    pub color: RBTreeNodeColor,
    pub key: RBTreeKey,
    pub value: RBTreeValue,
    pub parent: *mut RBTreeNode,
    pub children: [*mut RBTreeNode; 2],
}
pub type RBTreeKey = *mut libc::c_void;
pub type RBTreeNodeColor = libc::c_uint;
pub const RB_TREE_NODE_BLACK: RBTreeNodeColor = 1;
pub const RB_TREE_NODE_RED: RBTreeNodeColor = 0;
pub type RBTree = _RBTree;
pub type RBTreeNodeSide = libc::c_uint;
pub const RB_TREE_NODE_RIGHT: RBTreeNodeSide = 1;
pub const RB_TREE_NODE_LEFT: RBTreeNodeSide = 0;
extern "C" fn rb_tree_node_side(mut node: *mut RBTreeNode) -> RBTreeNodeSide {
    let boxed_node = unsafe { Box::from_raw(node) };
    let parent = unsafe { Box::from_raw((*boxed_node).parent) };
    let side = if parent.children[RB_TREE_NODE_LEFT as libc::c_int as usize] == node {
        RB_TREE_NODE_LEFT
    } else {
        RB_TREE_NODE_RIGHT
    };
    let _ = Box::into_raw(boxed_node);
    let _ = Box::into_raw(parent);
    side
}
extern "C" fn rb_tree_node_sibling(mut node: *mut RBTreeNode) -> *mut RBTreeNode {
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    let boxed_node = unsafe { Box::from_raw(node) };
    side = rb_tree_node_side(node);
    let sibling = unsafe {
        (*(*boxed_node).parent)
            .children[(1 as libc::c_int as libc::c_uint).wrapping_sub(side as libc::c_uint)
            as usize]
    };
    let node = Box::into_raw(boxed_node);
    sibling
}
#[no_mangle]
pub extern "C" fn rb_tree_node_uncle(
    mut node: *mut RBTreeNode,
) -> *mut RBTreeNode {
    let boxed_node = unsafe { Box::from_raw(node) };
    let uncle = rb_tree_node_sibling(boxed_node.parent);
    let node = Box::into_raw(boxed_node);
    uncle
}
extern "C" fn rb_tree_node_replace(
    mut tree: *mut RBTree,
    mut node1: *mut RBTreeNode,
    mut node2: *mut RBTreeNode,
) {
    let mut side: libc::c_int = 0;

    if !node2.is_null() {
        let mut boxed_node2 = unsafe { Box::from_raw(node2) };
        boxed_node2.parent = unsafe { (*node1).parent };
        node2 = Box::into_raw(boxed_node2);
    }

    if unsafe { (*node1).parent.is_null() } {
        let mut boxed_tree = unsafe { Box::from_raw(tree) };
        boxed_tree.root_node = node2;
        tree = Box::into_raw(boxed_tree);
    } else {
        side = rb_tree_node_side(node1) as libc::c_int;
        let mut boxed_parent = unsafe { Box::from_raw((*node1).parent) };
        boxed_parent.children[side as usize] = node2;
        unsafe {
            (*node1).parent = Box::into_raw(boxed_parent);
        }
    }
}
extern "C" fn rb_tree_rotate(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
    mut direction: RBTreeNodeSide,
) -> *mut RBTreeNode {
    let mut new_root: *mut RBTreeNode = std::ptr::null_mut();

    let mut boxed_node = unsafe { Box::from_raw(node) };
    new_root = boxed_node
        .children[(1 as libc::c_int as libc::c_uint)
        .wrapping_sub(direction as libc::c_uint) as usize];

    rb_tree_node_replace(tree, node, new_root);

    boxed_node
        .children[(1 as libc::c_int as libc::c_uint)
        .wrapping_sub(direction as libc::c_uint) as usize] = unsafe {
            (*new_root).children[direction as usize]
        };
    unsafe {
        (*new_root).children[direction as usize] = node;
        (*node).parent = new_root;
    }

    if !boxed_node
        .children[(1 as libc::c_int as libc::c_uint)
        .wrapping_sub(direction as libc::c_uint) as usize]
        .is_null()
    {
        unsafe {
            (*boxed_node
                .children[(1 as libc::c_int as libc::c_uint)
                .wrapping_sub(direction as libc::c_uint) as usize])
                .parent = node;
        }
    }

    node = Box::into_raw(boxed_node);
    new_root
}
#[no_mangle]
pub extern "C" fn rb_tree_new(
    compare_func: RBTreeCompareFunc,
) -> *mut RBTree {
    let new_tree: *mut RBTree = unsafe {
        alloc_test_malloc(std::mem::size_of::<RBTree>() as libc::c_ulong)
            as *mut RBTree
    };

    if new_tree.is_null() {
        return std::ptr::null_mut();
    }

    let mut boxed_tree = unsafe { Box::from_raw(new_tree) };
    boxed_tree.root_node = std::ptr::null_mut();
    boxed_tree.num_nodes = 0;
    boxed_tree.compare_func = compare_func;
    let new_tree = Box::into_raw(boxed_tree);

    new_tree
}
extern "C" fn rb_tree_free_subtree(mut node: *mut RBTreeNode) {
    if !node.is_null() {
        let boxed_node = unsafe { Box::from_raw(node) };
        rb_tree_free_subtree(boxed_node.children[RB_TREE_NODE_LEFT as libc::c_int as usize]);
        rb_tree_free_subtree(boxed_node.children[RB_TREE_NODE_RIGHT as libc::c_int as usize]);
        alloc_test_free(node as *mut libc::c_void);
        let node = Box::into_raw(boxed_node);
    }
}
#[no_mangle]
pub extern "C" fn rb_tree_free(mut tree: *mut RBTree) {
    if !tree.is_null() {
        let boxed_tree = unsafe { Box::from_raw(tree) };
        rb_tree_free_subtree(boxed_tree.root_node);
        alloc_test_free(tree as *mut libc::c_void);
        let tree = Box::into_raw(boxed_tree);
    }
}
extern "C" fn rb_tree_insert_case1(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let mut boxed_node = unsafe { Box::from_raw(node) };
    if boxed_node.parent.is_null() {
        boxed_node.color = RB_TREE_NODE_BLACK;
    } else {
        rb_tree_insert_case2(tree, node);
    }
    let node = Box::into_raw(boxed_node);
}
extern "C" fn rb_tree_insert_case2(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let boxed_node = unsafe { Box::from_raw(node) };
    if unsafe { (*(*boxed_node).parent).color as libc::c_uint != RB_TREE_NODE_BLACK as libc::c_int as libc::c_uint } {
        rb_tree_insert_case3(tree, node);
    }
    tree = Box::into_raw(boxed_tree);
    node = Box::into_raw(boxed_node);
}
extern "C" fn rb_tree_insert_case3(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let mut grandparent: *mut RBTreeNode = std::ptr::null_mut();
    let mut uncle: *mut RBTreeNode = std::ptr::null_mut();

    unsafe {
        grandparent = (*(*node).parent).parent;
        uncle = rb_tree_node_uncle(node);
    }

    if !uncle.is_null()
        && unsafe { (*uncle).color as libc::c_uint == RB_TREE_NODE_RED as libc::c_int as libc::c_uint }
    {
        unsafe {
            (*(*node).parent).color = RB_TREE_NODE_BLACK;
            (*uncle).color = RB_TREE_NODE_BLACK;
            (*grandparent).color = RB_TREE_NODE_RED;
        }
        rb_tree_insert_case1(tree, grandparent);
    } else {
        unsafe { rb_tree_insert_case4(tree, node); }
    }
}
extern "C" fn rb_tree_insert_case4(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let mut next_node: *mut RBTreeNode = std::ptr::null_mut();
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;

    let boxed_tree = unsafe { Box::from_raw(tree) };
    let boxed_node = unsafe { Box::from_raw(node) };

    side = rb_tree_node_side(node);
    if side as libc::c_uint != rb_tree_node_side(boxed_node.parent) as libc::c_uint {
        next_node = boxed_node.parent;
        rb_tree_rotate(
            tree,
            boxed_node.parent,
            (1 as libc::c_int as libc::c_uint).wrapping_sub(side as libc::c_uint)
                as RBTreeNodeSide,
        );
    } else {
        next_node = node;
    }

    rb_tree_insert_case5(tree, next_node);

    tree = Box::into_raw(boxed_tree);
    node = Box::into_raw(boxed_node);
}
extern "C" fn rb_tree_insert_case5(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let mut parent: *mut RBTreeNode = std::ptr::null_mut();
    let mut grandparent: *mut RBTreeNode = std::ptr::null_mut();
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;

    let boxed_node = unsafe { Box::from_raw(node) };
    let mut boxed_parent = unsafe { Box::from_raw(boxed_node.parent) };
    let mut boxed_grandparent = unsafe { Box::from_raw(boxed_parent.parent) };

    side = rb_tree_node_side(node);

    rb_tree_rotate(
        tree,
        boxed_grandparent.as_mut(),
        (1 as libc::c_int as libc::c_uint).wrapping_sub(side as libc::c_uint)
            as RBTreeNodeSide,
    );
    boxed_parent.color = RB_TREE_NODE_BLACK;
    boxed_grandparent.color = RB_TREE_NODE_RED;

    node = Box::into_raw(boxed_node);
    parent = Box::into_raw(boxed_parent);
    grandparent = Box::into_raw(boxed_grandparent);
}
#[no_mangle]
pub extern "C" fn rb_tree_insert(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
    mut value: RBTreeValue,
) -> *mut RBTreeNode {
    let mut node: *mut RBTreeNode = std::ptr::null_mut();
    let mut rover: *mut *mut RBTreeNode = std::ptr::null_mut();
    let mut parent: *mut RBTreeNode = std::ptr::null_mut();
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;

    let mut boxed_tree = unsafe { Box::from_raw(tree) };
    node = unsafe {
        alloc_test_malloc(std::mem::size_of::<RBTreeNode>() as libc::c_ulong) as *mut RBTreeNode
    };
    if node.is_null() {
        tree = Box::into_raw(boxed_tree);
        return std::ptr::null_mut();
    }
    let mut boxed_node = unsafe { Box::from_raw(node) };
    boxed_node.key = key;
    boxed_node.value = value;
    boxed_node.color = RB_TREE_NODE_RED;
    boxed_node.children[RB_TREE_NODE_LEFT as usize] = std::ptr::null_mut();
    boxed_node.children[RB_TREE_NODE_RIGHT as usize] = std::ptr::null_mut();
    parent = std::ptr::null_mut();
    rover = &mut boxed_tree.root_node;
    while !unsafe { (*rover).is_null() } {
        parent = unsafe { *rover };
        if unsafe {
            (boxed_tree.compare_func)
                .expect("non-null function pointer")(value, (**rover).value)
        } < 0
        {
            side = RB_TREE_NODE_LEFT;
        } else {
            side = RB_TREE_NODE_RIGHT;
        }
        rover = unsafe {
            &mut *((**rover).children).as_mut_ptr().offset(side as isize) as *mut *mut RBTreeNode
        };
    }
    unsafe {
        *rover = node;
    }
    boxed_node.parent = parent;
    rb_tree_insert_case1(tree, node);
    boxed_tree.num_nodes += 1;
    tree = Box::into_raw(boxed_tree);
    node = Box::into_raw(boxed_node);
    node
}
#[no_mangle]
pub extern "C" fn rb_tree_lookup_node(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
) -> *mut RBTreeNode {
    let mut node: *mut RBTreeNode = std::ptr::null_mut();
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    let mut diff: libc::c_int = 0;

    
    unsafe {
        node = (*tree).root_node;
    }

    while !node.is_null() {
        
        unsafe {
            diff = ((*tree).compare_func)
                .expect("non-null function pointer")(key, (*node).key);
        }

        if diff == 0 {
            return node;
        } else if diff < 0 {
            side = RB_TREE_NODE_LEFT;
        } else {
            side = RB_TREE_NODE_RIGHT;
        }

        
        unsafe {
            node = (*node).children[side as usize];
        }
    }

    return std::ptr::null_mut();
}
#[no_mangle]
pub extern "C" fn rb_tree_lookup(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
) -> RBTreeValue {
    let mut node: *mut RBTreeNode = std::ptr::null_mut();

    node = rb_tree_lookup_node(tree, key);

    if node.is_null() {
        return 0 as *mut libc::c_void;
    } else {
        let boxed_node = unsafe { Box::from_raw(node) };
        let value = boxed_node.value;
        let node = Box::into_raw(boxed_node);
        return value;
    }
}
#[no_mangle]
pub extern "C" fn rb_tree_remove_node(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
) {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let boxed_node = unsafe { Box::from_raw(node) };
    tree = Box::into_raw(boxed_tree);
    node = Box::into_raw(boxed_node);
}
#[no_mangle]
pub extern "C" fn rb_tree_remove(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
) -> libc::c_int {
    let mut node: *mut RBTreeNode = std::ptr::null_mut();

    node = rb_tree_lookup_node(tree, key);

    if node.is_null() {
        return 0;
    }

    rb_tree_remove_node(tree, node);

    return 1;
}
#[no_mangle]
pub extern "C" fn rb_tree_root_node(tree: *mut RBTree) -> *mut RBTreeNode {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let root_node = boxed_tree.root_node;
    let tree = Box::into_raw(boxed_tree);
    root_node
}
#[no_mangle]
pub extern "C" fn rb_tree_node_key(mut node: *mut RBTreeNode) -> RBTreeKey {
    let boxed_node = unsafe { Box::from_raw(node) };
    let key = boxed_node.key;
    let node = Box::into_raw(boxed_node);
    key
}
#[no_mangle]
pub extern "C" fn rb_tree_node_value(mut node: *mut RBTreeNode) -> RBTreeValue {
    let boxed_node = unsafe { Box::from_raw(node) };
    let value = boxed_node.value;
    let node = Box::into_raw(boxed_node);
    value
}
#[no_mangle]
pub extern "C" fn rb_tree_node_child(
    mut node: *mut RBTreeNode,
    mut side: RBTreeNodeSide,
) -> *mut RBTreeNode {
    if side as libc::c_uint == RB_TREE_NODE_LEFT as libc::c_int as libc::c_uint
        || side as libc::c_uint == RB_TREE_NODE_RIGHT as libc::c_int as libc::c_uint
    {
        let boxed_node = unsafe { Box::from_raw(node) };
        let child = boxed_node.children[side as usize];
        node = Box::into_raw(boxed_node);
        return child;
    } else {
        return std::ptr::null_mut();
    }
}
#[no_mangle]
pub extern "C" fn rb_tree_node_parent(
    mut node: *mut RBTreeNode,
) -> *mut RBTreeNode {
    let boxed_node = unsafe { Box::from_raw(node) };
    let parent = boxed_node.parent;
    let node = Box::into_raw(boxed_node);
    parent
}
#[no_mangle]
pub extern "C" fn rb_tree_to_array(mut tree: *mut RBTree) -> *mut RBTreeValue {
    return std::ptr::null_mut();
}
#[no_mangle]
pub extern "C" fn rb_tree_num_entries(mut tree: *mut RBTree) -> libc::c_int {
    let boxed_tree = unsafe { Box::from_raw(tree) };
    let num_nodes = boxed_tree.num_nodes;
    let tree = Box::into_raw(boxed_tree);
    num_nodes
}
